1. Field of the Invention
This invention relates to a method for determining the optimal placement of wavelength converters in optical networks and, more particularly, to a method for placing the minimum number of wavelength converters in a fiber optic network, all the while optimizing the bandwidth use. The invention maps minimal converters to support optimal bandwidth utilization in hierarchically structured fiber optic networks, including trees, trees of rings, forests, and any combination thereof connected networks.
2. Description of Prior Art
In wavelength-routed WDM (wavelengths-division multiplex) optical networks without any wavelength conversion, the wavelength assignment must meet the wavelength continuity constraint; that is, the same wavelength is allocated on all the links in the path established for a connection. However, this constraint can be relaxed when wavelength converters are placed at certain nodes. If a node of the network contains a wavelength converter, any path that passes through this node may change its wavelength. In a network with wavelength converters, the wavelengths are assigned to individual links of all paths, with the restriction that the same wavelength be allocated on all of the links in any subpath that does not pass through a wavelength converter. It is apparent that wavelength assignments in networks with wavelength converters can sometimes be more efficient, that is use fewer wavelengths, than optimal wavelength assignments for the same set of paths when no wavelength converters are available. One extreme example is that if each node contains a wavelength converter, the number of wavelengths required for any routing is reduced down to the natural congestion or load bound, defined to be the maximum number of paths passing through any one link in the network. Another extreme example is placement of a converter at a single arbitrary node in a WDM ring, which ensures that the number of wavelengths required for any routing is equal to its load.
This, in turn, raises the question as to the placement of wavelength converters in a WDM network so that any routing can be satisfied using no more wavelengths than if there were wavelength converters at every node. A set S of nodes in a network is defined to be sufficient if, placing converters at the nodes in S, every set of paths can be routed with a number of wavelengths equal to its congestion bound. The minimum sufficient set problem (MSSP) was shown to be NP-complete in general WDM networks. In Kleinberg, J. et al., xe2x80x9cWavelength Conversion in Optical Networksxe2x80x9d, Proceedings 10th ACM-SIAM Symposium On Discrete Algorithms, 1999, a tight connection between the minimum sufficient set problem in bi-directed graphs and the minimum vertex cover problem in undirected graphs was established. As a consequence of this connection, a simple two-approximation algorithm for a minimum sufficient set problem in bi-directed graphs was obtained. In addition, it is relatively easy to give an approximation-preserving reduction from the minimum vertex cover problem to the minimum sufficient set problem in bi-directed graphs.
While the teachings of Kleinberg, J. et al. set forth approximation solutions for general WDM networks, the topologies of most practical WDM networks are not general. In particular, trees and trees of rings are of more practical concrete relevance to the telecommunications industry. For practical reasons, backbone telecommunication networks need to reflect irregularity of geography, non-uniform clustering of users and traffic, hierarchy of services, dynamic growth, etc. In addition, wide-area multiwavelength technology is evolving around current signal wavelength networking architectures and existing fiber networks. These are mainly SONET rings and tree-like interconnection of such rings. (See, for example, Ballart, R. et al., xe2x80x9cSONET: Now its the standard optical networkxe2x80x9d, IEEE Communications Magazine, Pages 8-15, March 1989.)
We have found that the minimum sufficient set problem in these special topologies can be solved in polynomial time and, therefore, is not NP-complete. Our algorithms to find the minimum sufficient sets in these topologies are based on the reduction of the minimum sufficient set problem to the minimum vertex cover problem. These algorithms are very efficient and easy to implement.
It is one object of this invention to provide a method for determining the optimal placement of wavelength converters in a fiber optic network so as to utilize the minimum number of wavelength converters while optimizing the bandwidth use.
This and other objects of this invention are addressed by a method for determining an optimal placement of wavelength converters in an optical network while optimizing bandwidth use comprising the steps of generating a skeleton undirected graph of a WDM network, constructing a contraction graph from the skeleton undirected graph, and determining a minimum vertex cover of the contraction graph. This method is applicable to WDM networks comprising any of a number of underlining topologies including, but not limited to, trees, rings, trees of rings, forests and any combinations thereof.